package top.codetheory._05_二叉搜索树;

import java.util.Comparator;

/**
 * @author:
 * @since: 2023/12/28 14:24
 **/
public class BBST<E> extends BinarySearchTree<E> {
    public BBST() {
        this(null);
    }
    public BBST(Comparator<E> comparator) {
        super(comparator);
    }


    /**
     * 统一旋转
     * @param r 原来子树的根节点
     * @param a b的左
     * @param b d的左子树, 根节点
     * @param c b的右
     * @param d 旋转后的根节点
     * @param e f的左
     * @param f d的右子树, 根节点
     * @param g f的右
     */
    protected void rotate(
            Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g
    ) {
        // 让d成为这颗子树的根节点
        d.parent = r.parent;
        if (r.isLeftChildren()) {
            r.parent.left = d;
        } else if (r.isRightChildren()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // a - b - c
        b.left = a;
        b.right = c;
        if (a != null) {
            a.parent = b;
        }
        if (c != null ) {
            c.parent = b;
        }


        // e - f - g
        f.left = e;
        f.right = g;
        if (e != null) {
            e.parent = f;
        }
        if (g != null ) {
            g.parent = f;
        }


        // b - d - f
        d.left = b;
        d.right = f;
        b.parent = d;  // 这里不需要判空, 只有叶子节点才需要判空, b和f不是叶子节点
        f.parent = d;
    }

    /**   |                        |
     *   g                        p
     * /   \                    /   \
     *      p                  g     n2
     *    /  \               /  \
     *   n1   n2                 n1
     * 左旋
     * @param grand 爷爷节点
     */
    protected void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right; // 拿到父节点, 直接right就可以, 应为需要做旋的话, 那么right就一定是父节点
        Node<E> node = parent.left;  // n1 节点

        // 改变关键正向指针  三个, 一个指向p, 一个指向n, 一个指向n1
        grand.right = node;  // g的right指向n1
        parent.left = grand;  //p指向g
        afterRotate(grand, parent, node);
    }

    /**         |                  |
     *         g                  p
     *       /   \              /   \
     *     p                   n2    g
     *    /  \                     /  \
     *  n2   n1                   n1
     * 右旋
     * @param grand 爷爷节点
     */
    protected void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left; // 拿到父节点, 直接right就可以, 应为需要做旋的话, 那么right就一定是父节点
        Node<E> node = parent.right;  // n1 节点

        // 改变关键正向指针  三个, 一个指向p, 一个指向n, 一个指向n1
        grand.left = node;  // g的right指向n1
        parent.right = grand;  //p指向g
        afterRotate(grand, parent, node);
    }

    /**
     * 旋转之后的操作
     * @param grand 爷爷节点
     * @param parent 父节点
     * @param node n节点
     */
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> node) {
        if (grand.isLeftChildren()) {  // 如果是g是左子节点的话, 那么最上面那根线是 /
            grand.parent.left = parent;
        } else if (grand.isRightChildren()) {  // 是右子节点 \
            grand.parent.right = parent;
        } else {  // 没有parent grand是root节点
            root = parent;
        }

        // 维护parent 有三个, p的, g的, n1的
        parent.parent = grand.parent;  // p的
        grand.parent = parent;  // g的
        if (node != null) {  // n1的, 因为这里可能为null, 即没有这个子树, 所以要判断一下
            node.parent = grand;
        }
    }




}